package com.yehangtech.algorithm.算法基础篇.第一讲m基础算法._1_快速排序;

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 785. 快速排序
 * <p>
 * 给定你一个长度为 n的整数数列。
 * 请你使用快速排序对这个数列按照从小到大进行排序。
 * 并将排好序的数列按顺序输出。
 * <p>
 * 输入格式
 * 输入共两行，第一行包含整数 n。
 * 第二行包含 n个整数（所有整数均在 1∼109范围内），表示整个数列。
 * <p>
 * 输出格式
 * 输出共一行，包含 n个整数，表示排好序的数列。
 * <p>
 * 数据范围
 * 1≤n≤100000
 * <p>
 * 输入样例：
 * 5
 * 3 1 2 4 5
 * 输出样例：
 * 1 2 3 4 5
 */
public class 快速排序模板题 {

    static void quickSort(List<Integer> list, int left, int right) {
        if (left >= right) return;
        int i = left - 1;
        int j = right + 1;
        int x = list.get(i + j >> 1);
        while (i < j) {
            do i++; while (list.get(i) < x);
            do j--; while (list.get(j) > x);
            if (i < j) {
                int temp = list.get(i);
                list.set(i, list.get(j));
                list.set(j, temp);
            }
        }
        quickSort(list, left, j);
        quickSort(list, j + 1, right);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(in.nextInt());
        }
        quickSort(list, 0, n - 1);
        list.forEach(v -> System.out.print(v + " "));
    }
}
